package 牛客;

import 剑指offer.ListNode;

public class p链表分割 {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if (pHead==null) {
            return null;
        }
        //将 链表分为两部分，前一部分值比 x 小 ；后一部分值比 x 大或相等
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;

        while (pHead!=null) {
            if (pHead.val<x) {
                if (bs==null) {
                    bs=pHead;
                    be=bs;
                }else {
                    be.next=pHead;
                    be=be.next;
                }

            }else {
                if (as==null) {
                    as=pHead;
                    ae=as;
                }else {
                    ae.next=pHead;
                    ae=ae.next;
                }
            }
            pHead=pHead.next;
        }

        if (bs==null) {
            //没有前一部分数据时
            return as;
        }
        if (as!=null) {
            //当最后一个数据小于x，那么就要手动地把分好类的最后一个元素next置空
            ae.next=null;
        }
        be.next=as;
        return bs;
    }
}
